package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Two_Add_1 {
	
	public class ListNode {
	    int val;
	    ListNode next;
	    ListNode(int x) { val = x; }
	 }
	public static void main(String[] args) {
		int [] nums = {1,0,2};
		int target = 3;

		
		// System.out.println("hello");
	
	}

	// hashmap  key-value is a good thing ,we can use it to solve many qusetions
	public int[] twoSum(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		int[] result = { -1, -1 };
		for (int i = 0; i < nums.length; i++) {
			if (!map.containsKey(nums[i])) {
				int total = target - nums[i];
				map.put(total, i);
			} else {
				int first = map.get(nums[i]);
				result[0] = first;
				result[1] = i;
			}

		}
		return result;
	}

	public List<List<Integer>> threeSum(int[] nums) {

		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if (nums.length < 3)
			return result;

		Arrays.sort(nums);

		for (int i = 0; i < nums.length - 2; i++) {
			// advoid duplication
			if (i == 0 || nums[i] > nums[i - 1]) {
				int negate = -nums[i];
				int start = i + 1;
				int end = nums.length - 1;

				while (start < end) {
					if (nums[start] + nums[end] == negate) {

						List<Integer> list = new ArrayList<Integer>();

						list.add(nums[i]);
						list.add(nums[start]);
						list.add(nums[end]);
						result.add(list);
						start++;
						end--;
						// aviod duplication
						while (start < end && nums[end] == nums[end + 1]) {
							end--;
						}
						while (start < end && nums[start] == nums[start - 1]) {
							start++;
						}

					} else if (nums[start] + nums[end] < negate) {
						start++;
					} else {
						end--;
					}
				}
			}

		}
		return result;
	}

	public  int threeSumClosest(int[] nums, int target) {
		int result = 0;
		int min = Integer.MAX_VALUE;
		Arrays.sort(nums);
		for (int i = 0; i < nums.length - 2; i++) {
			int start = i + 1;
			int end = nums.length - 1;
			while (start < end) {
				int sum = nums[i] + nums[start] + nums[end];
				int diff = Math.abs(sum - target);
				if (diff == 0)
					return sum;
				if (diff < min) {
					min = diff;
					result = sum;
				}
				if(sum <= target){
					start++;
				}
				else{
					end--;
				}
			}
		}

		return result;

	}

	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode result = new ListNode(0);
		int carry = 0;
		
		
		return l2;
    }

}
